﻿// 版权所有：
// 文 件  名：Bubble.cs
// 功能描述：冒泡排序类
// 创建标识：Seven Song(m.sh.lin0328@163.com) 2014/5/01 20:00 已验证
// 修改描述：
//----------------------------------------------------------------*/
using System;
using System.Collections.Generic;

using System.Text;
using System.Collections;

namespace MSL.Utility.Sort
{
    /// <summary>
    /// 冒泡排序
    /// </summary>
    public class BubbleSort : SortBase, ISort
    {
        #region 改进的冒泡排序

        /// <summary>
        /// 冒泡排序（降序）原理：
        /// 从左到右以此比较两个相邻的数，若左小右大顺序则交换一下。这样，当一轮比较结束，最小的数就排在了最右边。
        /// 下一轮比较前N-1个数即可。 经过N-1轮比较，数列就是大->小排序的了。
        /// 改进的冒泡排序：当某轮比较没有发生移动时，就可以确定排序完成了，从而减少了排序的轮数。
        /// <para>稳定排序</para>
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Asc<T>(IList<T> list) where T : IComparable
        {
            if (list == null || list.Count == 0)
            {
                return;
            }
            bool isChange = false;
            for (int i = 1; i < list.Count; i++)
            {
                isChange = false;
                for (int j = list.Count - 1; j >= i; j--)
                {
                    if (list[j].CompareTo(list[j - 1]) < 0)
                    {
                        Swap(list, j, j - 1);
                        //当某轮比较没有发生移动时，就可以确定排序完成了
                        //否则应该继续排序
                        isChange = true;
                    }
                }
                if (!isChange)
                {
                    break;
                }
            }
        }

        /// <summary>
        /// 改进的冒泡排序：当某轮比较没有发生移动时，就可以确定排序完成了，从而减少了排序的轮数。
        /// <para>稳定排序</para>
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Desc<T>(IList<T> list) where T : IComparable
        {
            if (list == null || list.Count == 0)
            {
                return;
            }
            bool isChange = false;
            for (int i = 1; i < list.Count; i++)
            {
                isChange = false;
                for (int j = list.Count - 1; j >= i; j--)
                {
                    if (list[j].CompareTo(list[j - 1]) > 0)
                    {
                        Swap(list, j, j - 1);
                        //当某轮比较没有发生移动时，就可以确定排序完成了
                        //否则应该继续排序
                        isChange = true;
                    }
                }
                if (!isChange)
                {
                    break;
                }
            }
        }
        #endregion

        #region 鸡尾酒排序
        /// <summary>
        /// 鸡尾酒排序
        /// 原理：自左向右将大数冒到末尾，然后将剩余数列再自右向左将小数冒到开头，如此循环往复
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        /// <param name="isAsc">是否升序</param>
        public void CocktailDesc<T>(IList<T> list) where T : IComparable
        {
            bool flag;
            int m = 0, n = 0;
            for (int i = list.Count - 1; i > 0; i--)
            {
                flag = true;
                if (i % 2 == 0)
                {
                    for (int j = n; j < list.Count - 1 - m; j++)
                    {
                        if (list[j].CompareTo(list[j + 1]) < 0)
                        {
                            Swap(list, j, j + 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    m++;
                }
                else
                {
                    for (int k = list.Count - 1 - m; k > n; k--)
                    {
                        if (list[k].CompareTo(list[k - 1]) > 0)
                        {
                            Swap(list, k, k - 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    n++;
                }
            }
        }
        /// <summary>
        /// 
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        public void CocktailAsc<T>(IList<T> list) where T : IComparable
        {
            bool flag;
            int m = 0, n = 0;
            for (int i = list.Count - 1; i > 0; i--)
            {
                flag = true;
                if (i % 2 == 0)
                {
                    for (int j = n; j < list.Count - 1 - m; j++)
                    {
                        if (list[j].CompareTo(list[j + 1]) > 0)
                        {
                            Swap(list, j, j + 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    m++;
                }
                else
                {
                    for (int k = list.Count - 1 - m; k > n; k--)
                    {
                        if (list[k].CompareTo(list[k - 1]) < 0)
                        {
                            Swap(list, k, k - 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    n++;
                }
            }
        }
        #endregion
    }
}
